package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         30,
		Discription: "寻找所有串联所有单词的子串",
		Level:       3,
		Labels: map[string]int{
			"双指针滑动": 1,
			"滑动窗口":  1,
			"哈希表":   1,
		},
	})
}

func FindSubstring(s string, words []string) []int {
	wordMap := make(map[string]int, 0)
	for _, word := range words {
		wordMap[word]++
	}

	res := make([]int, 0)
	step := len(words[0])
	//只需遍历单个单词长度即可，后续窗口滑动以单词长度为单位
	for i := 0; i < step; i++ {
		count := len(words)
		left := i
		right := i + step
		tempWordMap := make(map[string]int, 0)
		for left < right && right <= len(s) {
			tempWord := s[right-step : right]
			totolNum, exist := wordMap[tempWord]
			if !exist {
				left = right
				right = left + step
				count = len(words)
				tempWordMap = make(map[string]int, 0)
				continue
			}

			//如果当前单词的匹配数超了，将left开始以单词长度为单位往右移动，直到刚好不超
			for tempWordMap[tempWord] >= totolNum {
				removedWord := s[left : left+step]
				tempWordMap[removedWord]--
				count++
				left += step
			}

			tempWordMap[tempWord]++
			count--
			//找到子串后，将left向右移动一个单词长度继续找
			if count == 0 {
				res = append(res, left)
				tempWordMap[s[left:left+step]]--
				count++
				left += step
			}
			right += step
		}
	}

	return res
}
